#pragma once
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
// #define max(a, b) (((a) > (b)) ? (a) : (b))
// #define min(a, b) (((a) > (b)) ? (b) : (a))
#define sign(x) ((x) > eps ? 1 : ((x) < -eps ? (-1) : (0)))
namespace qbe::auxiliary {
  
using namespace std;
const int MAXN = 1000;
const double eps = 1e-8, inf = 1e50, Pi = acos(-1.0);
struct point {
  double x, y;
  point() {}
  point(double _x, double _y) {
    x = _x;
    y = _y;
  }
  point operator-(const point& ne) const { return point(x - ne.x, y - ne.y); }
  point operator+(const point ne) const { return point(x + ne.x, y + ne.y); }
  point operator*(const double t) const { return point(x * t, y * t); }
  point operator/(const double t) const {
    if (sign(t) == 0)
      exit(1);
    return point(x / t, y / t);
  }
};
struct line {
  point a, b;
  line() {}
  line(point _a, point _b) {
    a = _a;
    b = _b;
  }
};
struct line2 {
  double a, b, c;
  line2() {}
  line2(double _a, double _b, double _c) {
    a = _a;
    b = _b;
    c = _c;
  }
};
struct circle {
  point o;
  double r;
  circle() {}
  circle(point _o, double _r) {
    o = _o;
    r = _r;
  }
};
struct rectangle {
  point a, b, c, d;
  rectangle() {}
  rectangle(point _a, point _b, point _c, point _d) {
    a = _a;
    b = _b;
    c = _c;
    d = _d;
  }
};
struct polygon {
  point p[MAXN];
  int n;
};
inline double xmult(point a, point b) {
  return a.x * b.y - a.y * b.x;
}
inline double xmult(point o, point a, point b) {
  return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
inline double xmult(double x1, double y1, double x2, double y2) {
  return x1 * y2 - x2 * y1;
}
inline double dmult(point o, point a, point b) {
  return (a.x - o.x) * (b.x - o.x) + (a.y - o.y) * (b.y - o.y);
}
inline double dmult(point a, point b) {
  return a.x * b.x + a.y * b.y;
}
inline double lenth(point a) {
  return sqrt(dmult(a, a));
}
inline double dist(point a, point b) {
  return lenth(b - a);
}
inline double dist2(point a, point b) {
  return dmult(b - a, b - a);
}
//直线一般式转两点式
line toline(double a, double b, double c);
//直线两点式转一般式
line2 toline2(point a, point b);
//点p绕o逆时针旋转alpha
point rotate(point o, point p, double alpha);
//向量u的倾斜角
double angle(point u);
//oe与os的夹角，夹角正负满足叉积
double angle(point o, point s, point e);

//判点在线段上
int p_on_seg(point a, point p1, point p2);
//判点在线段端点左方
int p_on_segvex(point s, point p);
//判线段相交 <=:不规范相交
int seg_inter(line s, line p);
//判点在多边形内部
int p_in_polygon(point a, point p[], int n);
}